package _剑指offer.二叉树;

import org.junit.Test;

import java.util.Arrays;
import java.util.PriorityQueue;
import java.util.Queue;

public class _40_最小的k个数 {
    @Test
    public void main() {
        int[] input = new int[] {1,3,4,5,8};
        System.out.println(Arrays.toString(getLeastNumbers(input, 3)));
    }
    
    public int[] getLeastNumbers(int[] arr, int k) {
        if (arr.length==0 || k==0) return new int[0];
        
        Queue<Integer> queue = new PriorityQueue<>( (v1,v2) -> v2-v1 );
        for (int i : arr) {
            if (queue.size() < k) {
                queue.add(i);
            } else {
                if (i < queue.peek()) {
                    queue.poll();
                    queue.add(i);
                }
            }
        }
        
        return queue.stream().mapToInt(Integer::valueOf).limit(k).toArray();
    }
}
